package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

import java.util.Locale;
import java.util.Stack;

/**
 * 二叉树中和为某一值的路径
 *
 * @author yuhushuan
 * @date 2020/6/22 00:02
 */
public class _34_1_PathInTree {
    private static void printPath(BinaryTreeNode root, int expectedSum) {
        printPath(root, expectedSum, "", 0);
    }

    private static void printPath(BinaryTreeNode node, int expectedSum,
                                  String path, int currentSum) {
        if (node == null) {
            return;
        }
        path += node.value + " ";
        currentSum += node.value;
        if (currentSum == expectedSum && node.left == null && node.right == null) {
            System.out.println(path);
        } else {
            printPath(node.left, expectedSum, path, currentSum);
            printPath(node.right, expectedSum, path, currentSum);
        }
    }

    private static void printPath_solution2(BinaryTreeNode root, int expectedSum) {
        printPath_solution2(root, expectedSum, new Stack<>(), 0);
    }

    private static void printPath_solution2(BinaryTreeNode node, int expectedSum,
                                            Stack<BinaryTreeNode> stack, int currentSum) {
        if (node == null) {
            return;
        }
        // 访问当前节点
        stack.push(node);
        currentSum += node.value;
        // 当前路径和为给定值
        if (currentSum == expectedSum && node.left == null && node.right == null) {
            printStack(stack);
        }
        if (node.left != null) {
            printPath_solution2(node.left, expectedSum, stack, currentSum);
        }
        if (node.right != null) {
            printPath_solution2(node.right, expectedSum, stack, currentSum);
        }
        // 在返回父节点之前，在路径上删除当前点
        stack.pop();
    }

    private static void printStack(Stack<BinaryTreeNode> stack) {
        if (stack == null || stack.isEmpty()) {
            return;
        }
        stack.forEach(node -> System.out.print(node.value + " "));
        System.out.println();
    }

    public static void main(String[] args) {
        BinaryTreeNode root = test1();

        // 功能测试
        // 有一条
        print(root, 19);
        // 有多条
        print(root, 22);
        // 没有
        print(root, 30);

        // 特殊输入测试 null
        print(null, 1);
    }

    private static void print(BinaryTreeNode root, int expectedSum) {
        System.out.println("二叉树：");
        BinaryTreeNode.drawBinaryTree(root);
        System.out.println(String.format(Locale.getDefault(),
                "预期为：%d 的路径为：", expectedSum));
        System.out.println("方法一：");
        printPath(root, expectedSum);
        System.out.println("方法二：");
        printPath_solution2(root, expectedSum);
        System.out.println();

    }

    private static BinaryTreeNode test1() {
        BinaryTreeNode n_10 = new BinaryTreeNode(10);
        BinaryTreeNode n_5 = new BinaryTreeNode(5);
        BinaryTreeNode n_12 = new BinaryTreeNode(12);
        BinaryTreeNode n_4 = new BinaryTreeNode(4);
        BinaryTreeNode n_7 = new BinaryTreeNode(7);

        n_10.left = n_5;
        n_10.right = n_12;

        n_5.left = n_4;
        n_5.right = n_7;


        return n_10;
    }
}
